First Lecture

• Originated in the late 1940’s when Richard Hamming became frustrated with a mechanical relay model at Bell Telephone Laboratories that would lose all his information whenever a single error occurred.
• Today, possible transmission errors: human error, cross talk, lightning, thermal noise, impulse noise, and deterioration.
• Now used in compact disc players, fax machines, modems and bar code scanners.
• Gallian’s example: Consider sending a message to a Martian lander that interprets a 0 as a command to land, and a 1 as a command to orbit. Transmission error could cause the wrong message to be sent, so we must have a redundancy method.

Formal Definition: An (n, k) linear code over a finite field F is a k-dimensional subspace of V of the vector space

Fⁿ = F Å F Å F … Å F

over F. The members of V are called the code words. A binary code would exist if n = 2.

The Hamming (7, 4) code (1948)

Message 0000 0001 0010 0100 1000 1100 1010 1001

Code Word 0000000 0001011 0010111 0100101 1000110 1100011 1010001 1001101

Message 0110 1010 0011 1110 1101 1011 0111 1111

Code Word 0110010 0101110 0011100 1110100 1101000 1011010 0111001 1111111

This code, devised by Richard Hamming, is unique because it has the potential to correct an error should one occur.

For instance, if the message received were 0000011, we would decode on the assumption that one error occurred in the 4^th spot, because the only expected code word that is within one number of the received word is 0001011. So we could deduce that the intended message was 0001.

We can illustrate how the Hamming (7, 4) code works by employing a Venn diagram. Essentially, this is three overlapping circles, which contain four shared areas. If we place our intended 4 digits inside each of these shared areas, the Hamming (7, 4) code works by placing the appropriate digits in the remaining spots in the independent portions of circles x A, B, and C so as to set the total sum of each circle equal to an even number. This summation trick is called a parity check.

If the message was sent to us, and we found that a circle contained an odd sum, we would know where to place the digit because of the interrelation between the circles. If only A summed to an odd number, we would know that the independent portion of A contained an error. If both A and B added up to an odd sum, we could deduce that the portion that is shared between A and B had an error during transmission.

The problem with both Hamming (7, 4) and the analogous Venn Diagram is that they are both faulty when more than one error occurs. To account for more than one error, codes with greater redundancy are needed.

Definition: Hamming distance – number of components in which two vectors differ.

Notation: d(u,v)

Definition: Hamming weight – minimum weight of any nonzero vector in the code.

Notation: wt(u)

Ex: u = 00011 v = 01001

u and v differ in 3 different locations, so d(u,v) = 3.

u has 2 non-zero digits, v has 3 non-zero digits, so wt(u) = 2, wt(v) = 2.

The reason we have these terms if because relationships exist between Hamming distance and Hamming weight. The most important Theorem follows:

For any vectors u, v, and w:

1. d(u, v) = wt(u – v)
2. d(u, v) c d(u, w) + d(w, v)

If the Hamming weight of a linear code is at least 2t + 1:

1. Then the code can correct any t or fewer errors.
2. Alternatively, the same code can detect any 2t or fewer errors.

Proof (a):

1. Suppose that a transmitted code word u is received as the vector v and that at most t errors have been made in transmission
2. By definition of distance between u and v, we have d(u,v) c t
3. Let w be any code word other than u
4. Then w – u is a nonzero code word.
5. So 2t + 1 c wt(w – u)
6. By Theorem 1a above, wt(w – u) = d(w, u)
7. By Theorem 1b above, d(w, u) c d(w, v) + d(v, u)
8. By step 2, we know that d(w, v) + d(v, u) c d(w, v) + t
9. Collectively, we’ve shown that 2t + 1 c d(w, v) + t
10. Simplified: t + 1 c d(w, v)

Proof (b):

1. Suppose we receive the vector v when u is intended.
2. Suppose at least one error, but no more than 2t errors, transmitted.
3. Because only code words are transmitted, an error will be detected

• Using redundancy increases the likelihood of a successful transmission.
• We can use algebraic coding to encode these redundancies in the most efficient manner possible.
• The type of algebraic code we are examining is called a linear code, expressed in the form (n,k)
• By analyzing concepts of Hamming distance and Hamming weight, we can determine the efficiency of these codes.

Message	Encoder G	Code Word
000 001 010 100 110 101 011 111	è è è è è è è è è	000000 001111 010101 100110 110011 101001 011010 111100

Consider the generator matrix of the Hamming (7, 4) code: G = [ 1 0 0 0 1 1 0 0 1 0 0 1 0 1 0 0 1 0 1 1 1 0 0 0 1 0 1 1 ]

The parity-check matrix of this generator is: [1 1 0 1 0 1 1 1 1 H = 0 1 1 1 0 0 0 1 0 0 0 1 ]

• Developed by David Slepian in 1956
• Conducted by constructing a standard array:

1. Calculate wH, the syndrome of w.
2. Find the coset leader v so that wH = vH
3. Assume that the vector sent was w – v.

• For the most part, we’ve only dabbled with Z₂. More complicated number sets are used also.
• Standard generator matrices are vulnerable to damage loss in bursts
• More sophisticated coding theory makes greater use of group theory, ring theory and especially finite-field theory.
• One example is the ESA probe Giotto which visited Halley’s Comet in 1986. It utilized two error correcting codes. One checked for independently occurring errors, of which our standard generator matrices are an example of. The other code was a Reed-Solomon code which checked for bursts of errors, as many as thousands of consecutive errors. This is the same method that is now used on compact discs.